package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.Stack;

/**
 * @author wei.zhao
 * @description: 判断一颗二叉树是否是搜索二叉树
 * @date 2022年02月23日 11:08
 */
public class Code06_IsSBT {

    public static Integer max = null;

    public static Boolean result = true;

    public static void main(String[] args) {
        Node head = new Node(7);
        head.left = new Node(5);
        head.right = new Node(9);
        head.left.left = new Node(4);
        head.left.right = new Node(6);
        head.right.left = new Node(8);
        head.right.right = new Node(10);
        System.out.println("递归方式：" + isBST01(head));
        System.out.println("非递归方式：" + isBST02(head));
        System.out.println("二叉树的递归套路：" + isBST03(head));
    }

    /* 递归方式 */
    private static boolean isBST01(Node head) {
        if (head == null) {
            return true;
        }
        traversal(head);
        return result;
    }

    private static void traversal(Node node) {
        if (node == null || !result) {
            return;
        }
        traversal(node.left);
        if (max == null || node.value > max) {
            max = node.value;
        } else {
            result = false;
        }
        traversal(node.right);
    }

    /* 非递归方式 */
    private static boolean isBST02(Node head) {
        if (head == null) {
            return true;
        }
        max = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || null != head) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                Node node = stack.pop();
                if (max > node.value) {
                    return false;
                } else {
                    max = node.value;
                }
                head = node.right;
            }
        }
        return true;
    }

    /* 二叉树的递归套路*/
    private static boolean isBST03(Node head) {
        Info info = process(head);
        return info.isS;
    }

    private static Info process(Node node) {
        if (node == null) {
            return new Info(true, null, null);
        }
        Info left = process(node.left);
        Info right = process(node.right);
        boolean result = true;
        if ((left.isS == false || right.isS == false)
                || (left.max != null && left.max > node.value)
                || right.min != null && right.min < node.value) {
            result = false;
        }
        Integer min = node.value;
        Integer max = node.value;
        min = left.min == null ? min : Math.max(left.min, min);
        max = right.max == null ? max : Math.max(right.max, max);
        return new Info(result, min, max);
    }

    private static class Info {
        public boolean isS;
        public Integer min;
        public Integer max;

        public Info(boolean isS, Integer min, Integer max) {
            this.isS = isS;
            this.min = min;
            this.max = max;
        }
    }


}
